//Given the head of a singly linked list and two integers left and right where l
//eft <= right, reverse the nodes of the list from position left to position right
//, and return the reversed list. 
//
// 
// Example 1: 
//
// 
//Input: head = [1,2,3,4,5], left = 2, right = 4
//Output: [1,4,3,2,5]
// 
//
// Example 2: 
//
// 
//Input: head = [5], left = 1, right = 1
//Output: [5]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the list is n. 
// 1 <= n <= 500 
// -500 <= Node.val <= 500 
// 1 <= left <= right <= n 
// 
//
// 
//Follow up: Could you do it in one pass? Related Topics 链表 
// 👍 915 👎 0


package leetcode.editor.cn;

//Java：Reverse Linked List II
class P92ReverseLinkedListIi {
    public static void main(String[] args) {
        Solution solution = new P92ReverseLinkedListIi().new Solution();
        // TO TEST
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(4);
//        ListNode node5 = new ListNode(5);
//        ListNode node6 = new ListNode(6);
        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//        node5.next = node6;
        solution.reverseBetween(node1, 1, 2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode root = head;
            ListNode startNode = null;
            ListNode startPreNode = null;
            ListNode endNextNode = null;
            ListNode endNode = null;
            ListNode preNode = null;
            int index = 0;
            while (root != null) {
                index++;
                if (startNode == null) {
                    startPreNode = preNode;
                }
                if (index == left) {
                    startNode = root;
                }
                if (index == right + 1) {
                    endNode = root;
                }
                preNode = root;
                root = root.next;
                if (endNode == null) {
                    endNextNode = root;
                }

            }
            //反转a与b之间的链表
            ListNode pre = endNextNode, cur = startNode, nxt;
            while (cur != endNode) {
                nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }
            if (startPreNode != null) {
                startPreNode.next = pre;
                return head;
            } else {
                return pre;
            }
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}